package treeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

//后序遍历

/**
 * 首先遍历左子树，然后遍历右子树，最后访问根结点，
 * 在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。
 */
public class Solution12 {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> ret = new LinkedList<Integer>();
        //递归方法，
        if(root==null){
            return ret;
        }
        postorderTraversal(root,ret);

        return ret;
    }

    private void postorderTraversal(TreeNode root, LinkedList<Integer> ret) {
        if(root==null){
            return ;
        }
        if(root.left!=null){
            postorderTraversal(root.left,ret);
        }
        if(root.right!=null){
            postorderTraversal(root.right,ret);
        }
        ret.add(root.val);
    }

    public static void main(String[] args) {
        /**
         *                 1
         *              /     \
         *             2            3
         *            / \        /      \
         *          4   5       6       7
         *       / \   / \     / \     /  \
         *      8  9  10  11  12  13  14   15
         */
        TreeNode root = TreeNodeUtils.getTestTreeNode();
        Solution12 solution = new Solution12();
        System.out.println(solution.postorderTraversal(root));

    }
}
